package 代码随想2._6栈与队列;

/**
 * @author XXX
 * @date 2024-01-17 16:55
 */

import java.util.ArrayDeque;

/**
 * https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
 */
public class _4删除字符串中的所有相邻重复项 {
    public String removeDuplicates(String s) {
        ArrayDeque<Character> dq = new ArrayDeque<>();
        char ch;
        for (int i=0; i<s.length();i++){
            ch = s.charAt(i);
            if (dq.isEmpty() || dq.peek()!=ch)
                dq.push(ch);
            else
                dq.pop();
        }

        String str = "";
        while (!dq.isEmpty())
            str = dq.pop() + str;
        return str;
    }

    public String removeDuplicates2(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(sb.length()==0 || sb.charAt(sb.length()-1)!=s.charAt(i))
                sb.append(s.charAt(i));
            else{
                sb.deleteCharAt(sb.length()-1);
            }
        }
        return sb.toString();
    }

    //双指针
    public String removeDuplicates3(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while(fast < s.length()){
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if(slow > 0 && ch[slow] == ch[slow - 1]){
                slow--;
            }else{
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}
